package algorithm.array;

import java.util.HashMap;
import java.util.Map;

/**
 * leetcode : https://leetcode.com/problems/two-sum/description/
 * Difficulty: Easy
 *
 * 给一个数组，和一个目标target.
 * 数组里的两个元素 nums[i] + nums[j] = target
 * 求一个数组 [i,j]
 * 注意，是求数组中的索引。所以不能用ThreeSum中的 排序想法
 *
 * 但其实这个更简单
 *
 * 暴力解法是O(N^2) 显然不可取
 * 其实只需要一个Map,存储已经遍历过的元素即可, key=nums的值, value=index
 * @Author Antony
 * @Since 2018/7/5 22:55
 */
public class TwoSum {



    // (leetcode beats 99.93%)
    public static int[] twoSum(int[] nums, int target) {
        int[] arr = new int[2];
        Map<Integer,Integer> map = new HashMap<>();
        int tmp;
        for(int i=0; i<nums.length; i++){
            tmp = target - nums[i];
            Integer index = map.get(tmp);
            if(index != null){
                arr[0] = index;
                arr[1] = i;
                return arr;
            }else{
                map.put(nums[i], i);
            }
        }
        return arr;
    }
}
